package grafo;

import java.io.FileOutputStream;
import java.util.ArrayList;
import java.util.Random;
import javax.swing.JFileChooser;

/**
 *
 * @author Alexandre
 * @author Lucas 
 * 
 * Classe que gerencia os vértices e arestas, e busca o caminho mínimo
 * 
 */
public class Grafo {

    public static int idVertices;
    public static ArrayList<Vertice> Vertices;
    public static ArrayList<Integer> MenorCaminho;
    public static ArrayList<Tabela> tabela;
    
    int XMax, YMax; //Tamanho máximo de X e Y
    public static int NumArestasPorVertice;
    static String caminho = System.getProperty("user.dir") + "\\src\\Arquivos";
    Random gerador = new Random();

    public Grafo(int _XMax, int _YMax) {
        Vertices = new ArrayList<>();
        idVertices = 0;
        XMax = _XMax;
        YMax = _YMax;
        MenorCaminho = new ArrayList<>();
        tabela = new ArrayList<>();
    }

    /*
     *   Construtor usado quando criar o grafo a partir de um arquivo
     */
    public Grafo() {
        Vertices = new ArrayList<>();
    }

    public int getXMax() {
        return XMax;
    }

    public void setXMax(int XMax) {
        this.XMax = XMax;
    }

    public int getYMax() {
        return YMax;
    }

    public void setYMax(int YMax) {
        this.YMax = YMax;
    }

    /**
     * Adiciona um vertice com id e coordenadas definidas
     *
     * @param id
     * @param x
     * @param y
     */
    public void addVertice(int id, int x, int y) {
        Vertices.add(new Vertice(id, x, y));
    }

    /**
     * Adiciona um vertice com coordenadas aleatórios
     */
    public void addVertice() {
        int x, y;
        x = gerador.nextInt(XMax);
        y = gerador.nextInt(YMax);

        boolean pertence = true;
        int cont = 0;

        //Verifica se já existe algum vértice com estas coordenadas
        while (pertence) {
            for (Vertice Vertice : Vertices) {
                if (x == Vertice.getX() && y == Vertice.getY()) {
                    ++cont;
                }
            }
            if (cont > 0) {
                x = gerador.nextInt(XMax);
                y = gerador.nextInt(YMax);
                cont = 0;
            } else {
                pertence = false;
            }
        }
        Vertices.add(new Vertice(Grafo.idVertices, x, y));
        ++Grafo.idVertices;
    }

    /**
     * Adiciona arestas com origem e destino definidos, usado ao abrir um grafo
     * do arquivo
     *
     * @param idO id origem
     * @param idD id destino
     */
    public void addAresta(int idO, int idD) {
        for (Vertice Vertice : Vertices) {
            if (Vertice.getIdVertice() == idO) {
                Vertice.addAresta(idD);
            }
        }
    }

    /**
     * Adiciona arestas randomicamente
     *
     * @param idO id de Origem
     */
    public void addAresta(int idO) {
        int idD;
        boolean inseriu = false;
        idD = gerador.nextInt(Vertices.size());
        for (Vertice Vertice : Vertices) {
            if (Vertice.getIdVertice() == idO) {
                while (!inseriu) {
                    inseriu = Vertice.addAresta(idD);
                    idD = gerador.nextInt(Vertices.size());
                }
            }
        }
    }

    /**
     * Imprime todos os vértices e arestas
     */
    public void Show() {
        for (Vertice Vertice : Vertices) {
            System.out.println("Vertice: " + Vertice.getIdVertice());
            System.out.println("Coordenadas ( " + Vertice.getX() + ", " + Vertice.getY() + ")");
            Vertice.ShowArestas();
        }
    }

    /**
     *
     * @param id = id do Vértice Exibe todas as arestas do vértice com o id
     * informado
     */
    public void Conexoes(int id) {
        for (Vertice Vertice : Vertices) {
            if (Vertice.getIdVertice() == id) {
                System.out.println("Vertice: " + Vertice.getIdVertice());
                Vertice.ShowArestas();
            }
        }
    }

    /**
     * Imprime toda a lista de adjacência
     */
    public void ShowListaAdjacencia() {
        for (Vertice Vertice : Vertices) {
            Vertice.ShowListaAdjacencia();
        }
    }

    /**
     * Salva o grafo em um arquivo
     *
     * @throws java.lang.Exception
     */
    public void save() throws Exception {
        if (Vertices.isEmpty()) {
            System.out.println("Não existe vértices");
            return;
        }
        JFileChooser chooser = new JFileChooser(caminho);
        chooser.showSaveDialog(null);
        FileOutputStream in = new FileOutputStream(chooser.getSelectedFile());

        for (Vertice Vertice : Vertices) {
            String grava = Vertice.getIdVertice() + ";" + Vertice.getX()
                    + ";" + Vertice.getY() + ";" + Vertice.getsize() + ";"
                    + Vertice.ListaArestas() + "\n";

            //salva no arquivo
            in.write(grava.getBytes());
        }
    }

    /**
     * Procura o custo de uma aresta
     *
     * @param idOrigem
     * @param idDestino
     * @return retorna o custo
     */
    public double buscaCusto(int idOrigem, int idDestino) {
        for (Vertice Vertice : Vertices) {
            if (Vertice.getIdVertice() == idOrigem) {
                for (Aresta Aresta : Vertice.Arestas) {
                    if (Aresta.getIdDestino() == idDestino) {
                        return Aresta.getCusto();
                    }
                }
            }
        }
        return -1; // significa que não existe a aresta
    }

    /**
     * 
     * @param id id do vértice a buscar o nó anterior
     * @return retorna o id do nó anterior no menor caminho
     */
    public int buscaNoAnterior(int id) {
        for (int i = 0; i < tabela.size(); i++) {
            if (tabela.get(i).caminho.contains(id)) {
                return (tabela.get(i - 1).listaNode.get(id).getAnterior());
            }
        }
        return -1;
    }

    /**
     * Implementação do algoritmo de Djikstra
     *
     * @param idInicial = id do vértice de origem
     * @param idFinal = id do vértice de destino
     */
    public void djikstra(int idInicial, int idFinal) {
        if (idInicial == idFinal) { //destino e origem no mesmo ponto
            return;
        }

        tabela.add(new Tabela());
        tabela.get(0).caminho.add(idInicial);
        tabela.get(0).listaNode.get(idInicial).setCusto(0);

        //Inicialização
        for (Vertice Vertice : Vertices) {
            if (Vertice.getIdVertice() == idInicial) {
                for (Aresta Aresta : Vertice.Arestas) {
                    tabela.get(0).listaNode.get(Aresta.getIdDestino()).setCusto(Aresta.Custo);
                    tabela.get(0).listaNode.get(Aresta.getIdDestino()).setAnterior(idInicial);
                }
            }
        }

        int menor;
        double custoAnt;
        double novoCusto;

        //início do loop para preencher o resto da tabela
        for (int i = 1; i < Vertices.size(); i++) {
            if(tabela.get(tabela.size()-1).caminho.contains(idFinal)){//Para de preencher a tabela djikstra quando encontra o caminho mínimo
                break;
            }
            menor = tabela.get(tabela.size() - 1).getMenor(); //id do menor custo na tabela anterior
            if (menor != -1) {
                tabela.add(new Tabela());
                custoAnt = tabela.get(tabela.size() - 2).listaNode.get(menor).getCusto(); //pega o menor custo até o elemento menor
                tabela.get(tabela.size() - 1).caminho.addAll(tabela.get(tabela.size() - 2).caminho); //copia o caminho percorrido anteriormente para o vetor atual
                tabela.get(tabela.size() - 1).caminho.add(menor); // adiciona o menor no caminho

                for (int j = 0; j < Vertices.size(); j++) {
                    if (tabela.get(tabela.size() - 1).caminho.contains(j)) { //se o vértice já estiver no caminho, o custo é 0
                        tabela.get(tabela.size() - 1).listaNode.get(j).setCusto(0);
                    } else {
                        //Se tiver aresta do vértice que entrou no caminho para o vértice j,
                        // calcula o custo e compara se é menor que o anterior, 
                        // caso não haja aresta ele copia o valor anterior da tabela
                        if (buscaCusto(menor, j) != -1) { 
                            novoCusto = custoAnt + buscaCusto(menor, j);
                            if (novoCusto < tabela.get(tabela.size() - 2).listaNode.get(j).getCusto() || tabela.get(tabela.size() - 2).listaNode.get(j).getCusto() == -1) {
                                tabela.get(tabela.size() - 1).listaNode.get(j).setCusto(novoCusto);
                                tabela.get(tabela.size() - 1).listaNode.get(j).setAnterior(menor);
                            } else {
                                tabela.get(tabela.size() - 1).listaNode.get(j).setCusto(tabela.get(tabela.size() - 2).listaNode.get(j).getCusto());
                                tabela.get(tabela.size() - 1).listaNode.get(j).setAnterior(tabela.get(tabela.size() - 2).listaNode.get(j).getAnterior());
                            }
                        } else {
                            tabela.get(tabela.size() - 1).listaNode.get(j).setCusto(tabela.get(tabela.size() - 2).listaNode.get(j).getCusto());
                            tabela.get(tabela.size() - 1).listaNode.get(j).setAnterior(tabela.get(tabela.size() - 2).listaNode.get(j).getAnterior());
                        }
                    }
                }
            } else {
                break;
            }
        }

        //Imprime tabela djikstra no terminal
        /*for (int j = 0; j < tabela.size(); j++) {
         tabela.get(j).showCaminho();
         for (int i = 0; i < tabela.get(0).listaNode.size(); i++) {
         System.out.println("id = " + i + "\tcusto = " + tabela.get(j).listaNode.get(i).custo);
         }
         }
         System.out.println("");*/
       
        System.out.println(tabela.get(tabela.size() - 2).listaNode.get(idFinal).getCusto());
        
        /**
         * Buscando o menor caminho na matriz djikstra
         */
        int ant;
        if (tabela.get(tabela.size() - 1).caminho.contains(idFinal)) { //Verificando se existe caminho
            MenorCaminho.add(idFinal);
            ant = idFinal;
            while (ant != idInicial) {
                ant = buscaNoAnterior(ant);
                MenorCaminho.add(ant);
            }
        } else {
            System.out.println("Não existe caminho");
        }

        //Imprime o caminho no terminal
        System.out.print("Caminho: \t");
        for (Integer MenorCaminho1 : MenorCaminho) {
            System.out.print(MenorCaminho1 + "\t");
        }
        System.out.println("");
    }
}
